package hot_100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @author: Darven
 * @createTime: 2025-09-25  22:17
 * @description: TODO
 */
public class P56 {
    public static void main(String[] args) {
        P56 p56 = new P56();
        int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        int[][] result = p56.merge(intervals);

        // 打印结果
        for (int[] arr : result) {
            System.out.println(Arrays.toString(arr));
        }
    }

    //    public int[][] merge(int[][] intervals) {
//        if(intervals.length<=1){
//            return intervals;
//        }
//        Arrays.sort(intervals, Comparator.comparing(a->a[0]));
//        List<int[]> ans=new ArrayList<>();
//        int[] current=intervals[0];
//        ans.add(current);
//        for(int i=1;i<intervals.length;i++){
//            int lr = current[1];
//            int rl=intervals[i][0];
//            int end=intervals[i][1];
//            if(lr>=rl){
//                current[1]=Math.max(lr, end);
//            }else{
//                current=intervals[i];
//                ans.add(current);
//            }
//        }
//        return ans.toArray(new int[ans.size()][]);
//    }
    // 最后差分法有问题不适合这个合并数组，最后还是排序加判断
    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) {
            return intervals;
        }
        int minStart = Integer.MAX_VALUE;
        int maxEnd = Integer.MIN_VALUE;
        for (int[] interval : intervals) {
            minStart = Math.min(minStart, interval[0]);
            maxEnd = Math.max(maxEnd, interval[1]);
        }
        int[] diff = new int[maxEnd-minStart+2];
        int offset = minStart;
        List<int[]> ans=new ArrayList<>();

        for (int i = 0; i < intervals.length; i++) {
            int start = intervals[i][0];
            int end = intervals[i][1];
            if(start!=end){
                diff[start - offset] += 1;
                diff[end - offset] -= 1;
            }
        }
        int currentCover=0;
        int startSite=-1;
        for (int i=0;i<diff.length;i++){
            currentCover+=diff[i];
            if(currentCover>0&&startSite==-1){
                // 开始
                startSite=i;
            }else if (currentCover==0&&startSite!=-1){
                ans.add(new int[]{startSite+offset,i+offset});
                startSite=-1;
            }
        }
        return ans.toArray(new int[ans.size()][]);

    }

}
